#ifndef Lista_
#define Lista_

#include "Node.h"
#include <string>

using namespace std;

template <class T> 
class List_Iterator ;

template<class T>
class List
{
	friend List_Iterator<T>;
    
	private:

		Node<T> *head ;

		void destroylist();

	public:
		List() ;
		List(const List<T>& l);
		virtual ~List();
		bool empty() const;
		virtual void  insert(int k, const T & elem);
		void remove(int k, T  &x);
		void find (int k, T &x) const ;
		int length() const;

		const List<T>& operator = (const List<T> & l) ;

		void write (ostream& out) const ;
};

template <class T>
List<T>::List(){
	head = NULL;
}

template <class T>
List<T>::List(const List<T>& l){
	Node<T> * newptr =new Node<T>;

	if(l.head)
		head=newptr;
	else 
	    head=NULL;   
	
	Node<T> * auxptr = l.head;

	while (auxptr)
	{
		newptr->info=auxptr->info;
		if(auxptr->next== NULL)
		{
			newptr->next=NULL;
			auxptr=auxptr->next;
		}
		else
		{
			newptr->next = new Node<T>;
			newptr = newptr->next;
			auxptr = auxptr->next;
		}
	}
}

template <class T>
List<T>::~List(){
	destroylist();
}

template<class T>
void List<T>::destroylist(){
	Node<T> * temp;

	while(head)
	{
		temp=head->next;
		delete head;
		head=temp;
	}
	head = NULL ; 
}


template <class T>
bool List<T>::empty() const{
	return (head==NULL);
}

template <class T>
void  List<T>::insert(int k, const T & elem){
	if (k <= 0)
		cout << "Posicao invalida ! \n" ;
	else
	{
		Node<T>* newptr= new Node<T> ;
		newptr->info=elem;

		Node<T> *temp=head;

		if (k == 1)
		{
			newptr->next = temp ;
			head = newptr;
		}
		else
		{
 		  int i=1; 
		  while (i < k-1 && temp)
		  {
			temp=temp->next;
			i++;
		  }
          if (temp)
		  {
			newptr->next=temp->next;
			temp->next=newptr;
		  }
		}
	}
}

template <class T>
int List<T>::length() const{
	Node<T> *temp;

	int length=0;

	temp = head;
	while (temp)
	{
		length++;
		temp=temp->next;
	}
	return length;
}

template<class T>
void List<T>::find (int k, T &x) const{
	int leng = length () ;

	if (k > 0 &&  k <= leng) 
	{
		Node<T> * ptr=head;

		for (int i = 1; i < k ; i++)
			ptr = ptr->next ;   

		if (ptr)
			x = ptr->info ;
	}
} 

template<class T>
void  List<T>::remove (int k, T  &x)
{
  if (k <= 0 || k > legth()) 
	  cout << "Posicao invalida ! \n" ;
  else
  {
	  Node<T> * act=head ;
	  Node<T> * bef=NULL ;

	  for (int i = 1; i < k && act; i++)
	  {
		  bef = act ;
		  act = act->next ;
	  }
	  
	  if (bef) 
	    bef->next = act->next ;
      else
		head = head->next ;

	  x = act->info ;
	  delete act ;
  }
}

template <class T>
const List<T>& List<T>::operator = (const List<T> &l)
{

	if (this == &l)
		return *this;

	destroylist();

	Node<T> * auxptr = l.head;
    int i = 1 ; 

	while (auxptr != NULL)
	{
		insert(i,auxptr->info) ;
		i++ ;
		auxptr=auxptr->next;
	}
 	return *this;
}

template<class T>
void List<T>::write(ostream& out) const
{
	Node<T>* temp = head;
	if (head)
		do
		{  
			out << temp->info << "  ";
			temp=temp->next;
		} while (temp);
	else
		out << "Lista Vazia";
	out << endl;
}

template<class T>
ostream& operator << (ostream& out, const List<T>& l) 
{
	l.write(out) ;
	return out ;
}


#endif